"""
654. 最大二叉树 - 算法测试框架

用于测试两种算法的正确性和性能
"""

import time
import sys
from typing import List, Tuple
from alg import Solution, TreeNode, tree_to_list, print_tree_preorder
from gen import TestDataGenerator, analyze_array_properties

class AlgorithmTester:
    """算法测试器"""
    
    def __init__(self):
        self.solution = Solution()
        self.generator = TestDataGenerator()
    
    def test_correctness(self) -> bool:
        """测试算法正确性"""
        print("=" * 60)
        print("算法正确性测试")
        print("=" * 60)
        
        all_passed = True
        test_cases = self.generator.generate_all_test_cases()
        
        for i, (name, nums) in enumerate(test_cases[:10], 1):  # 只测试前10个用例
            print(f"\n测试用例 {i}: {name}")
            print(f"输入: {nums}")
            
            try:
                # 递归方法
                start_time = time.time()
                root1 = self.solution.constructMaximumBinaryTree_recursive(nums.copy())
                recursive_time = time.time() - start_time
                result1 = tree_to_list(root1)
                
                # 单调栈方法
                start_time = time.time()
                root2 = self.solution.constructMaximumBinaryTree(nums.copy())
                stack_time = time.time() - start_time
                result2 = tree_to_list(root2)
                
                # 验证结果
                is_same = result1 == result2
                all_passed = all_passed and is_same
                
                print(f"递归方法结果: {result1}")
                print(f"单调栈方法结果: {result2}")
                print(f"结果一致: {'✓' if is_same else '✗'}")
                print(f"递归法用时: {recursive_time:.6f}s")
                print(f"单调栈法用时: {stack_time:.6f}s")
                
                if not is_same:
                    print("❌ 测试失败！")
                    return False
                    
            except Exception as e:
                print(f"❌ 测试出错: {e}")
                all_passed = False
        
        print(f"\n{'✅ 所有测试通过！' if all_passed else '❌ 部分测试失败'}")
        return all_passed
    
    def test_performance(self):
        """性能测试"""
        print("\n" + "=" * 60)
        print("算法性能测试")
        print("=" * 60)
        
        # 性能测试用例
        performance_cases = [
            ("小规模", list(range(10, 0, -1))),
            ("中等规模", list(range(50, 0, -1))),
            ("大规模", list(range(100, 0, -1))),
        ]
        
        print(f"{'测试用例':<12} {'数组长度':<8} {'递归法(s)':<12} {'单调栈法(s)':<12} {'加速比':<8}")
        print("-" * 60)
        
        for name, nums in performance_cases:
            # 递归方法
            start_time = time.time()
            self.solution.constructMaximumBinaryTree_recursive(nums.copy())
            recursive_time = time.time() - start_time
            
            # 单调栈方法
            start_time = time.time()
            self.solution.constructMaximumBinaryTree(nums.copy())
            stack_time = time.time() - start_time
            
            speedup = recursive_time / stack_time if stack_time > 0 else float('inf')
            
            print(f"{name:<12} {len(nums):<8} {recursive_time:<12.6f} {stack_time:<12.6f} {speedup:<8.2f}")
    
    def test_special_cases(self):
        """测试特殊用例"""
        print("\n" + "=" * 60)
        print("特殊用例测试")
        print("=" * 60)
        
        special_cases = [
            ("空数组", []),
            ("单元素", [42]),
            ("两元素递增", [1, 2]),
            ("两元素递减", [2, 1]),
            ("完全递增", [1, 2, 3, 4, 5]),
            ("完全递减", [5, 4, 3, 2, 1]),
            ("V形", [3, 1, 4]),
            ("山形", [1, 4, 2]),
        ]
        
        for name, nums in special_cases:
            print(f"\n{name}: {nums}")
            
            if not nums:  # 空数组特殊处理
                print("空数组，跳过测试")
                continue
            
            try:
                # 分析数组性质
                props = analyze_array_properties(nums)
                print(f"最大值: {props.get('max_value', 'N/A')} (位置: {props.get('max_position', 'N/A')})")
                
                # 测试算法
                root1 = self.solution.constructMaximumBinaryTree_recursive(nums.copy())
                root2 = self.solution.constructMaximumBinaryTree(nums.copy())
                
                result1 = tree_to_list(root1)
                result2 = tree_to_list(root2)
                
                print(f"结果: {result1}")
                print(f"算法一致性: {'✓' if result1 == result2 else '✗'}")
                
            except Exception as e:
                print(f"测试出错: {e}")
    
    def verify_tree_properties(self, nums: List[int], root: TreeNode) -> bool:
        """验证构建的树是否满足最大二叉树性质"""
        if not nums or not root:
            return not nums and not root
        
        # 验证根节点是最大值
        max_val = max(nums)
        if root.val != max_val:
            return False
        
        max_idx = nums.index(max_val)
        
        # 验证左子树
        left_nums = nums[:max_idx]
        if left_nums:
            if not root.left or not self.verify_tree_properties(left_nums, root.left):
                return False
        else:
            if root.left:
                return False
        
        # 验证右子树
        right_nums = nums[max_idx + 1:]
        if right_nums:
            if not root.right or not self.verify_tree_properties(right_nums, root.right):
                return False
        else:
            if root.right:
                return False
        
        return True
    
    def test_tree_properties(self):
        """测试树的性质"""
        print("\n" + "=" * 60)
        print("二叉树性质验证")
        print("=" * 60)
        
        test_cases = [
            [3, 2, 1, 6, 0, 5],
            [3, 2, 1],
            [1, 2, 3, 4, 5],
            [5, 4, 3, 2, 1],
        ]
        
        for i, nums in enumerate(test_cases, 1):
            print(f"\n测试用例 {i}: {nums}")
            
            # 递归方法构建的树
            root1 = self.solution.constructMaximumBinaryTree_recursive(nums.copy())
            is_valid1 = self.verify_tree_properties(nums, root1)
            
            # 单调栈方法构建的树
            root2 = self.solution.constructMaximumBinaryTree(nums.copy())
            is_valid2 = self.verify_tree_properties(nums, root2)
            
            print(f"递归法构建的树满足性质: {'✓' if is_valid1 else '✗'}")
            print(f"单调栈法构建的树满足性质: {'✓' if is_valid2 else '✗'}")
    
    def run_all_tests(self):
        """运行所有测试"""
        print("654. 最大二叉树 - 完整测试套件")
        print("=" * 60)
        
        try:
            # 1. 正确性测试
            if not self.test_correctness():
                print("❌ 正确性测试失败，停止后续测试")
                return False
            
            # 2. 特殊用例测试
            self.test_special_cases()
            
            # 3. 树性质验证
            self.test_tree_properties()
            
            # 4. 性能测试
            self.test_performance()
            
            print("\n" + "=" * 60)
            print("✅ 所有测试完成！")
            print("=" * 60)
            
            return True
            
        except Exception as e:
            print(f"❌ 测试过程中出错: {e}")
            return False

def main():
    """主测试函数"""
    tester = AlgorithmTester()
    
    print("选择测试模式:")
    print("1. 完整测试")
    print("2. 只测试正确性")
    print("3. 只测试性能")
    print("4. 只测试特殊用例")
    
    try:
        choice = input("请选择 (1-4): ").strip()
        
        if choice == "1":
            tester.run_all_tests()
        elif choice == "2":
            tester.test_correctness()
        elif choice == "3":
            tester.test_performance()
        elif choice == "4":
            tester.test_special_cases()
        else:
            print("运行完整测试...")
            tester.run_all_tests()
            
    except KeyboardInterrupt:
        print("\n测试被用户中断")
    except Exception as e:
        print(f"测试出错: {e}")

if __name__ == "__main__":
    main()